package algorithm.tree;

import algorithm.tree.bst.TreeNode;
import org.junit.Before;
import org.junit.Test;

import java.util.Stack;

/**
 * 使用 非递归的方式 深度遍历树
 */
public class DFS {


    public static void main(String[] args) {
        // 创建一个简单的树结构
//     1
//    / \
//   2   3
//  / \
// 4   5
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        // 使用非递归的深度优先搜索前序遍历
        dfsPreOrder(root);
        System.out.println();
        dfsInOrder(root);
        System.out.println();
        postorderTraversal(root);
    }

    /**
     * @param root
     */
    private static void dfsPreOrder(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            System.out.println(pop.val);
            if (pop.right != null) {
                stack.push(pop.right);
            }
            if (pop.left != null) {
                stack.push(pop.left);
            }

        }
    }

    /**
     * 中序遍历
     */
    private static void dfsInOrder(TreeNode root) {

        // current 指针,沿着该指针从左节点一直往下遍历
        TreeNode current = root;
        Stack<TreeNode> stack = new Stack<>();
        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            //如果 current 指针为空 就回溯
            TreeNode pop = stack.pop();
            System.out.println(pop.val);

            //如果当前节点 有右子节点。 设置 current 指针 指向右节点，从而进行遍历
            if (pop.right != null) {
                current = pop.right;
            }
        }
    }

    private static void postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode visited = null;
        //指针, 指针不为空就一直沿着左节点往下遍历
        TreeNode current = root;
        while (current != null || !stack.isEmpty()) {
            if (current != null) {
                //往下遍历
                while (current != null) {
                    stack.push(current);
                    current = current.left;
                }

            } else {
                TreeNode peek = stack.peek();
                if (peek.right != null && peek.right.val != visited.val) {
                    // 存在右节点,开始遍历右节点
                    current = peek.right;
                } else {
                    // 出栈,相当于回溯
                    TreeNode pop = stack.pop();

                    visited = pop;
                    System.out.println(pop.val);
                }
            }
        }
    }

    TreeNode root;

    @Before
    public void test() {
        root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
    }

    @Test
    public void test1() {
        // 创建一个简单的树结构
        //     1
        //    / \
        //   2   3
        //  / \
        // 4   5
        test1pre(root);
    }

    //20240307 前序遍历
    public void test1pre(TreeNode root) {
        //堆栈
        Stack<TreeNode> stack = new Stack<>();

        TreeNode current = root;
        while (current != null) {
            System.out.println(current.val);
            if (current.right != null) {
                stack.push(current.right);
            }
            if (current.left != null) {
                current = current.left;
            } else {
                if (!stack.isEmpty())
                    current = stack.pop();
                else
                    current = null;
            }

        }

    }


}
